#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include <conio.h>
#include <windows.h>
using namespace std;

struct coordinate
{
	int x,y,dir;
};

void Fix()
{
	HANDLE hOut;
	CONSOLE_CURSOR_INFO curInfo;
	COORD P={0,0};
	hOut=GetStdHandle(STD_OUTPUT_HANDLE);
	SetConsoleCursorPosition(hOut,P);
	SetConsoleCursorInfo(hOut,&curInfo);
}

class Union
{
	private:
		int fa[16385];
		bool check[32513];
		int Find(int id)
		{
			return fa[id]=(fa[id]==id?id:Find(fa[id]));
		}
	public:
		void Initialize(int row_size,int col_size)
		{
			int i;
			for(i=1;i<=(row_size+1)*(col_size+1)/4;i++) fa[i]=i;
			memset(check,0,sizeof(check));
		}
		coordinate Query(int id,int row_size,int col_size)
		{
			coordinate temp;
			if(id<=(row_size+1)*(col_size-1)/4)
			{
				temp.x=2*((id-1)/((col_size-1)/2))+1;
				temp.y=2*((id-1)%((col_size-1)/2))+2;
				temp.dir=0;
			}
			else 
			{
				temp.x=row_size-2*((id-(row_size+1)*(col_size-1)/4-1)%((row_size-1)/2))-1;
				temp.y=2*((id-(row_size+1)*(col_size-1)/4-1)/((row_size-1)/2))+1;
				temp.dir=1;
			}
			return temp;
		};
		int* SummonRandomSequence(int len)
		{
			int cnt=len,temp,*seq;
			seq=new int[len];
			srand((signed)time(NULL));
			while(cnt)
			{
				temp=rand()%len+1;
				if(!check[temp]) check[temp]=true,seq[cnt--]=temp;
			}
			return seq;
		}
		bool Judge(int row_size,int col_size,coordinate pos)
		{
			int temp1,temp2,u,v;
			if(!pos.dir)
			{
				temp1=(pos.x/2)*((col_size+1)/2)+pos.y/2;
				temp2=(pos.x/2)*((col_size+1)/2)+pos.y/2+1;
			}
			else 
			{
				temp1=(pos.x/2-1)*((col_size+1)/2)+(pos.y+1)/2;
				temp2=(pos.x/2)*((col_size+1)/2)+(pos.y+1)/2;
			}
			u=Find(temp1),v=Find(temp2);
			if(u!=v)
			{
				fa[v]=u;
				return true;	
			}
			else return false;
		}
}sys;

class Maze
{
	public:
		int row_size,col_size;
		char Map[257][257];
		void Initialize()
		{
			int i,j;
			memset(Map,' ',sizeof(Map));
			printf("Please input the number of rows and columns of maze respectively, separated by space:\n");
			scanf("%d%d",&row_size,&col_size);
			while(!(row_size%2)||!(col_size%2))
			{
				printf("Both row and column should be odd numbers!\n");
				scanf("%d%d",&row_size,&col_size);
			}
			sys.Initialize(row_size,col_size);
			for(i=0;i<=col_size+1;i+=2) for(j=0;j<=row_size+1;j++) Map[j][i]='#';
			for(i=0;i<=row_size+1;i+=2) for(j=1;j<=col_size;j++) Map[i][j]='#';
			Map[1][0]=Map[row_size][col_size+1]='>';
			Map[1][1]='0';
		}
		void Summon()
		{
			int i,*seq=sys.SummonRandomSequence((row_size*col_size-1)/2);
			coordinate temp;
			for(i=1;i<=(row_size*col_size-1)/2;i++) if(sys.Judge(row_size,col_size,temp=sys.Query(seq[i],row_size,col_size))) Map[temp.x][temp.y]=' ';
		}
		void Print()
		{
			int i,j;
			Fix();
			for(i=0;i<=row_size+1;i++)
			{
				for(j=0;j<=col_size+1;j++) putchar(Map[i][j]);
				putchar('\n');
			}
		}
		void Reset()
		{
			Initialize();
			Summon();
		}
}Level;

class Control
{
	public:
		coordinate pos;
		void Reset()
		{
			pos.x=pos.y=1;
		}
		bool Escape()
		{
			return pos.x==Level.row_size&&pos.y==Level.col_size;
		}
		void Move(char ch)
		{
			Fix();
			Level.Map[pos.x][pos.y]=' ';
			if(ch=='w'&&(Level.Map[pos.x-1][pos.y]==' '||Level.Map[pos.x-1][pos.y]=='1')) pos.x--;
			if(ch=='a'&&(Level.Map[pos.x][pos.y-1]==' '||Level.Map[pos.x][pos.y-1]=='1')) pos.y--;
			if(ch=='s'&&(Level.Map[pos.x+1][pos.y]==' '||Level.Map[pos.x+1][pos.y]=='1')) pos.x++;
			if(ch=='d'&&(Level.Map[pos.x][pos.y+1]==' '||Level.Map[pos.x][pos.y+1]=='1')) pos.y++;
			Level.Map[pos.x][pos.y]='0';
			Level.Print();
		}
}Player;

class Help
{
	private:
		int xx[4],yy[4];
		bool show,find,check[257][257];
		vector<coordinate> path,ans;
		void dfs(coordinate now)
		{
			int i;
			coordinate temp;
			if(now.x==Level.row_size&&now.y==Level.col_size) 
			{
				ans=path;
				find=true;
				return ;
			}
			for(i=0;!find&&i<4;i++) 
			{
				temp=now;
				temp.x+=xx[i]; temp.y+=yy[i];
				if(!check[temp.x][temp.y]&&Level.Map[temp.x][temp.y]!='#'&&Level.Map[temp.x][temp.y]!='>') 
				{
					check[temp.x][temp.y]=true;
					path.push_back(temp);
					dfs(temp);
					check[temp.x][temp.y]=false;
					path.pop_back();
				}
			}
		}
	public:
		void Reset()
		{
			xx[0]=1,xx[1]=0,xx[2]=-1,xx[3]=0;
			yy[0]=0,yy[1]=1,yy[2]=0,yy[3]=-1;
			find=false;
			memset(check,0,sizeof(check));
			path.clear();
			ans.clear();
		}
		void Path(coordinate pos)
		{
			int i;	
			Reset();
			check[pos.x][pos.y]=true;
			dfs(pos);
			if(!show)
			{
				Fix();
				for(i=0;i<ans.size();i++) Level.Map[ans[i].x][ans[i].y]='1';
				Level.Print();
				show=true;
			}
			else 
			{
				Fix();
				for(i=0;i<ans.size();i++) Level.Map[ans[i].x][ans[i].y]=' ';
				Level.Print();
				show=false;
			}
		}
}Solution;

int main()
{
	char ch;
	clock_t start,end;
	Level.Reset();
	Player.Reset();
	Solution.Reset();
	system("cls");
	MessageBox(0,"Press OK to start the game","SYSTEM",MB_OK);
	start=clock();
	Level.Print();
	while(!Player.Escape()) if(_kbhit())
	{
		ch=_getch();
		if(ch=='h') Solution.Path(Player.pos);
		else if(ch=='w'||ch=='a'||ch=='s'||ch=='d') Player.Move(ch);
	}
	end=clock();
	printf("You Win!!!Solved in %.2lf seconds\n",double(end-start)/CLOCKS_PER_SEC);
	system("pause");
	return 0;
}
